/**
 * 1020. 飞地的数量
 * https://leetcode-cn.com/problems/number-of-enclaves/
 */
public class Solutions_1020 {
    public static void main(String[] args) {
//        int[][] A = {{0, 0, 0, 0},
//                     {1, 0, 1, 0},
//                     {0, 1, 1, 0},
//                     {0, 0, 0, 0}};  // output: 3

        int[][] A = {{0, 1, 1, 0},
                     {0, 0, 1, 0},
                     {0, 0, 1, 0},
                     {0, 0, 0, 0}};  // output: 0

        int result = numEnclaves(A);
        System.out.println(result);
    }

    private static int row = 0, col = 0;

    /**
     * 1. 遍历最上行和最下行，最左列和最右列，即网格的边界
     * 2. 若单元格为 1，那么从该处开始深度优先搜索，
     *      若存在与其相邻的陆地，那么与其相邻的陆地也是可以离开网格的边界的
     * 3. 将网格的边界上的 1 和与其相邻的 1，都标记为 0
     * 4. 最终网格中 1 的数量就是无法离开网格边界的陆地单元格的数量
     */
    public static int numEnclaves(int[][] A) {
        row = A.length;
        col = A[0].length;

        for (int i = 0; i < col; i++) {
            // 遍历最上下的行
            if (A[0][i] == 1) {
                dfs(A, 0, i);
            }
            if (A[row - 1][i] == 1) {
                dfs(A, row - 1, i);
            }
        }
        for (int i = 0; i < row; i++) {
            // 遍历最左右的列
            if (A[i][0] == 1) {
                dfs(A, i, 0);
            }
            if (A[i][col - 1] == 1) {
                dfs(A, i, col - 1);
            }
        }
        int res = 0;
        for (int[] arr : A) {
            for (int k : arr) {
                res += k;
            }
        }
        return res;
    }

    public static void dfs(int[][] mat, int i, int j) {
        if (i < 0 || i >= row || j < 0 || j >= col || mat[i][j] == 0) {
            return;
        }
        mat[i][j] = 0;
        // 上
        dfs(mat, i - 1, j);
        // 下
        dfs(mat, i + 1, j);
        // 左
        dfs(mat, i, j - 1);
        // 右
        dfs(mat, i, j + 1);
    }
}
